home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group01a.txt / 000023_icon-group-sender _Fri May 19 12:25:07 2000.msg < prev    next >
Internet Message Format  |  2002-01-03  |  5KB
  1. Return-Path: <icon-group-sender>
  2. Received: (from root@localhost)
  3.     by baskerville.CS.Arizona.EDU (8.9.1a/8.9.1) id MAA02361
  4.     for icon-group-addresses; Fri, 19 May 2000 12:24:33 -0700 (MST)
  5. Message-Id: <200005191924.MAA02361@baskerville.CS.Arizona.EDU>
  6. From: espie@liafa.jussieu.fr (Marc Espie)
  7. X-Newsgroups: comp.lang.icon
  8. Subject: Re: Is Anyone Working On A Unicode Version Of Icon?
  9. Date: 19 May 2000 15:09:30 GMT
  10. X-Trace: vishnu.jussieu.fr 958748970 2780 132.227.81.128 (19 May 2000 15:09:30 GMT)
  11. X-Complaints-To: Newsmaster@jussieu.fr.
  12. X-Newsreader: trn 4.0-test70 (17 January 1999)
  13. To: icon-group@optima.CS.Arizona.EDU
  14. Errors-To: icon-group-errors@optima.CS.Arizona.EDU
  15. Status: RO
  16. Content-Length: 3699
  17.  
  18. In article <200005172324.QAA19139@baskerville.CS.Arizona.EDU>,
  19. Ian Trudel <ian.trudel@tr.cgocable.ca> wrote:
  20. >> >5/ and finaly, speed issue only speaks by benchmarking.
  21. >> I've run some fairly large icon projects in the past. I have a fairly good
  22. >> idea about what slowed them down eventually. I even have a submitted paper
  23. >> to a conference that pits icon against maple and C++.
  24. >
  25. >Now that's interesting, is your paper online?
  26.  
  27. Not yet, sorry. There are proceedings involved, and I'll have to see if
  28. there is red tape involved with Springer.
  29.  
  30. Briefly put, the gist of the matter was to compare methods to generate
  31. Dyck words (well-parenthesized words).
  32.  
  33. I asked a friend who is a typical user of maple to write it in a way natural
  34. to maple, which I compared to the typical icon generator:
  35.  
  36. procedure dyck(n)
  37.     if n = 0 then
  38.         suspend ""
  39.     else
  40.         every i := 0 to n-1 do
  41.             suspend "("||dyck(i)||")"||dyck(n-i-1)
  42. end
  43.  
  44. As far as C++ goes, I exposed a simple technique to `revert' generators 
  45. control, e.g, model
  46. every write(gen())
  47. as an `application of' every(write(.))  to gen.
  48.  
  49. The traditional icon implementation does have write call gen repetitively.
  50. Instead, we have gen produce results and pass them to a `continuation' of
  51. write that tells whether it needs more results. This combines nicely with
  52. the Template Method design pattern, and leads to an almost automatic
  53. translation to C++ that does not need any extra control structures to handle
  54. generators (e.g., the program flow is more or less hardcoded into templates).
  55.  
  56. For Dyck words, the results looks like (more or less, generator.h left
  57. aside for brevity):
  58.  
  59. #include <string>
  60. #include "generator.h"
  61.  
  62. class DyckWord3: public Function<string> {
  63.     const Function<string>& f; const string& b;
  64. public:
  65.     DyckWord3(const string& b_, const Function<string>& f_):
  66.         f(f_), b(b_) {}
  67.     bool operator() (const string& e) const {
  68.         return f(b+e);
  69.     }
  70. };
  71. class DyckWord2: public Generator<string> { const string& a; int r;
  72. public:
  73.     DyckWord2(const string& a_, int r_): a(a_), r(r_) {}
  74.     bool iterate(const Function<string>& consume) const;
  75. };
  76. class DyckWord1: public Function<string> {
  77.     const Function<string>& f; const int n;
  78. public:
  79.     DyckWord1(const Function<string>& f_, int n_): f(f_), n(n_) {}
  80.     bool operator()(const string &a) const {
  81.         return DyckWord2("("+a+")", n).iterate(f);
  82.     }
  83. };
  84. class DyckWord: public Generator<string> { const int n;
  85. public:
  86.     DyckWord(int n_): n(n_) {}
  87.     bool iterate(const Function<string>& consume) const {
  88.         if (n == 0) return consume("");
  89.         else for (int i = 0; i < n; i++)
  90.                 if (!DyckWord(i).iterate(DyckWord1(consume, n-1-i)))
  91.                     return false;
  92.         return true;
  93.     }
  94. }; 
  95. bool DyckWord2::iterate(const Function<string>& consume) const {
  96.         return DyckWord(r).iterate(DyckWord3(a, consume));
  97. }
  98.  
  99.  
  100. Granted, this is somewhat longer than the icon version.
  101.  
  102. Both the Icon and C++ version outperform Maple by a huge factor (as maple
  103. is not geared toward generators, and the traditional Dyck word generator
  104. is memory-heavy).  Somewhat surprisingly, the C++ implementation is not much
  105. faster than the Icon implementation (factor of 3).  This was traced down
  106. to the particular C++ string implementation not being well-suited to the job
  107. at hand.  
  108.  
  109. In similar cases where strings are not involved and where memory consumption
  110. can be taken out of the way (permutations, with in-place list construction),
  111. C++ outperforms icon by a factor of 10 or more, which is quite logical.
  112.  
  113. The Icon compiler does not gain that much, which was to be expected as well.
  114. -- 
  115.     Marc Espie        
  116. |anime, sf, juggling, unicycle, acrobatics, comics...
  117. |AmigaOS, OpenBSD, C++, perl, Icon, PostScript...
  118. | `real programmers don't die, they just get out of beta'
  119.